package com.itcam.sort.bucketsort;

import com.itcam.sort.insertsort.InsertionSort;

import java.util.Arrays;

/**
 * @author : Cammy.Wu
 * Description : 桶排序-改进
 */

public class BucketSortGeneric {
    public static void main(String[] args) {
//        int[] ages = {20, 18, 28, 66, 25, 31, 67, 30};
        int[] ages = {9, 0, 5, 1, 3, 2, 4, 6, 8, 7};
        System.out.println(Arrays.toString(ages));
        bucketSort(ages, 3);
        System.out.println(Arrays.toString(ages));
    }

    /*
        0   0,1,2
        1   3,4,5
        2   6,7,8
        3   9,10,11
     */
    public static void bucketSort(int[] ages, int range) {
        int max = ages[0];
        int min = ages[0];
        for (int i = 1; i < ages.length; i++) {
            if (ages[i] > max) {
                max = ages[i];
            }
            if (ages[i] < min) {
                min = ages[i];
            }
        }
        // 1.准备桶
        DynamicArray[] buckets = new DynamicArray[(max - min) / range + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new DynamicArray();
        }

        // 2.放入年龄数据
        for (int age : ages) {
            buckets[(age - min) / range].addLast(age);
        }
        int k = 0;
        for (DynamicArray bucket : buckets) {
            System.out.println(Arrays.toString(bucket.array()));
            // 3.排序桶内元素
            int[] array = bucket.array();
            InsertionSort.insertion(array);
            // System.out.println(Arrays.toString(array));
            for (int v : array) {
                ages[k++] = v;
            }
        }
    }
}
